Repetitive structures are ubiquitous not only in nature, e.g. in biology and physics, but also in other fields, such as engineering and art. Repetitive structures are very common in man-made objects, and fundamental e.g. in almost all design styles in architecture. Therefore, all common types of 3D mesh models generally comprise repetitive structures. Due to increasing complexity of such models, it is desirable to minimize the amount of data required for coding them. It has been found that symmetry, including repetitive structures, is a kind of redundancy that may be used to reduce complexity: Repetitive structures need to be encoded only once, and can be called or “instantiated” several times. In order to benefit from this redundancy, it is necessary to detect repetitive structures in existing 3D mesh models. Traditional methods use a technique for segmenting periodic structures that relies on a user to manually identify repetitive elements. Obviously such user assistance is unwanted.
Each instance of a repetitive structure can be individually modified by transformations, such as rotations, translations, reflections and uniform scaling. A known method1 for (partial) symmetry detection, even at different scales, uses an approach that is called “transformation voting”: it comprises constructing a transformation space, clustering possible transformations and deciding symmetry by transformation clusters. E.g. Mitra1 calculates in a first step local shape descriptors, which are then used to pair up points that could be mapped to each other under a candidate symmetry action. A set of possible candidate transformations is called transformation space. Pairs with similar transformations form clusters in the transformation space, which provide evidence for the corresponding symmetry relation. In a second step, point pairs whose transformation falls into a cluster are checked for spatial consistency. A stochastic clustering provides surface correspondences, so that only a small set of candidates samples needs to be considered when detecting and extracting symmetric surface patches. Curvature descriptors are used to pair sample points; candidate point pairs are discarded if their curvature descriptors differ too much. Similarly, it is known2 to group sample points into “similarity sets” according to curvature descriptors. Curvature is generally the amount by which a geometric object deviates from being flat.
One reason for the usage of clustering is that the amount of data to be compared is very high. The number of sampling points, and thus the data amount, highly depends on the sampling step size: smaller sampling steps result in more data, which makes the clustering steps less efficient. However, larger sampling steps result in the omission of small-scale structures.